package leetcode;

public class leetcode107 {
//    原答案（错误 ）
//    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//
//        List<Integer> l=new ArrayList<>();
//        List<List<Integer>> ls=new ArrayList<>();
//
//        if(root==null){
//            return null;
//        }
//        while (root!=null){
//            if(root.left!=null){
//                l.add(root.left.val);
//                root=root.left;
//            }
//            if(root.right!=null){
//                l.add(root.right.val);
//                root=root.right;
//            }
//            ls.add(l);
//
//        }
//
//        l.add(root.val);
//        ls.add(l);
//        return ls;
//    }


//    BFS
//public class Solution {
//    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//        Queue<TreeNode> queue = new LinkedList<TreeNode>();
//        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
//
//        if(root == null) return wrapList;
//
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            int levelNum = queue.size();
//            List<Integer> subList = new LinkedList<Integer>();
//            for(int i=0; i<levelNum; i++) {
//                if(queue.peek().left != null) queue.offer(queue.peek().left);
//                if(queue.peek().right != null) queue.offer(queue.peek().right);
//                subList.add(queue.poll().val);
//            }
//            wrapList.add(0, subList);
//        }
//        return wrapList;
//    }
//}


//    DFS
//    public class Solution {
//        public List<List<Integer>> levelOrderBottom(TreeNode root) {
//            List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
//            levelMaker(wrapList, root, 0);
//            return wrapList;
//        }
//
//        public void levelMaker(List<List<Integer>> list, TreeNode root, int level) {
//            if(root == null) return;
//            if(level >= list.size()) {
//                list.add(0, new LinkedList<Integer>());
//            }
//            levelMaker(list, root.left, level+1);
//            levelMaker(list, root.right, level+1);
//            list.get(list.size()-level-1).add(root.val);
//        }
//    }
}
